package main

import "fmt"

func main() {
	fmt.Println(lengthOfLIS([]int{1, 3, 6, 7, 9, 4, 10, 5, 6}))
	fmt.Println(lengthOfLIS([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 200, 300, 300, 4909, 500, 600}))
}

func lengthOfLIS(nums []int) int {
	//最长递增子序列,定义dp[i]为以第i个元素结尾的最长递增子序列, 每个元素是子序列的长度
	var dp = make([]int, 0, len(nums))
	//所有以第i个元素结尾的最长递增子序列元素初始化为1
	for _, _ = range nums {
		dp = append(dp, 1)
	}
	maxSum := 1
	//只要比当前元素小的子序列长度 + 1 大于dp【i】存储的已经循环过的最大长度，就把最大长度替换成+1的那个长度。
	for i, v := range nums {
		for j := 0; j < i; j++ {
			if v > nums[j] && dp[j]+1 > dp[i] {
				dp[i] = dp[j] + 1
				if dp[i] > maxSum {
					maxSum = dp[i]
				}
			}
		}
	}
	return maxSum
}
